package com.LeeCode;

/**
 * 统计按位或能得到最大值的子集数目
 */

public class Code2044 {
    public static void main(String[] args) {
        int[] nums = {3, 2, 1, 5};
        System.out.println(new Code2044().countMaxOrSubsets(nums));
    }

    private int ans = 0;
    private int maxVal = Integer.MIN_VALUE;

    public int countMaxOrSubsets(int[] nums) {
        int totalOr = 0;
        for (int num : nums) {
            totalOr |= num;
        }
        backtrace(0, 0, nums, totalOr);
        return ans;
    }

    private void backtrace(int index, int cur, int[] nums, int totalOr) {
        if (cur == totalOr) {
            ans += 1 << (nums.length - index);
            return;
        }
        if (index == nums.length) return;
        backtrace(index + 1, cur, nums, totalOr);
        backtrace(index + 1, cur | nums[index], nums, totalOr);
    }

    public int countMaxOrSubsets1(int[] nums) {
        backtrace(0, 0, nums, 0);
        return ans;
    }

    private void backtrace1(int index, int cur, int[] nums, int count) {
        if (index == nums.length) {
            if (count == 0) return;
            if (maxVal < cur) {
                maxVal = cur;
                ans = 1;
            } else if (maxVal == cur) {
                ans++;
            }
            return;
        }

        backtrace(index + 1, cur, nums, count);
        backtrace(index + 1, cur | nums[index], nums, count + 1);
    }
}
